package com.cg.leetcode;

import org.junit.Test;

import java.util.HashMap;
import java.util.Map;

/**
 * 567.字符串的排列
 *
 * @program: LeetCode->LeetCode_567
 * @author: cg
 * @create: 2022-04-16 15:36
 **/
public class LeetCode_567 {

    @Test
    public void test567() {
        System.out.println(checkInclusion("ab", "eidbaooo"));
        System.out.println(checkInclusion("ab", "eidboaoo"));
    }

    /**
     * 给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。
     * <p>
     * 换句话说，s1 的排列之一是 s2 的 子串 。
     * <p>
     * 示例 1：
     * 输入：s1 = "ab" s2 = "eidbaooo"
     * 输出：true
     * 解释：s2 包含 s1 的排列之一 ("ba").
     * <p>
     * 示例 2：
     * 输入：s1= "ab" s2 = "eidboaoo"
     * 输出：false
     * <p>
     * 提示：
     * 1 <= s1.length, s2.length <= 10^4
     * s1 和 s2 仅包含小写字母
     *
     * @param s1
     * @param s2
     * @return
     */
    public boolean checkInclusion(String s1, String s2) {
        Map<Character, Integer> window = new HashMap<>(), need = new HashMap<>();
        // 初始化子串每个字符的个数
        for (int i = 0; i < s1.length(); i++) {
            need.put(s1.charAt(i), need.getOrDefault(s1.charAt(i), 0) + 1);
        }
        // 建立索引，valid为满足数量的字符个数
        int left = 0, right = 0, valid = 0;
        while (right < s2.length()) {
            // 因为right从0开始，所以先取字符再移动索引
            // 获取右边新进窗口的字符
            char rightCh = s2.charAt(right);
            // 右边窗口索引+1
            right++;
            // 当前字符为子串中所需的字符
            if (need.containsKey(rightCh)) {
                // 将当前字符加入到窗口中
                window.put(rightCh, window.getOrDefault(rightCh, 0) + 1);
                // 如果当前字符的数量与子串所需的数量相同，即当前字符数量以满足
                if (need.get(rightCh).equals(window.get(rightCh))) {
                    // 满足的字符个数+1
                    valid++;
                }
            }

            // 固定窗口大小
            while (right - left >= s1.length()) {
                // 如果当前满足的字符数量与所需的字符相等就返回
                if (valid == need.size()) {
                    return true;
                }
                // 获取左边界将要删除的字符
                char leftCh = s2.charAt(left);
                // 左边窗口索引-1
                left++;
                if (need.containsKey(leftCh)) {
                    // 如果当前字符的数量与子串所需的数量相同，即当前字符数量以满足
                    if (need.get(leftCh).equals(window.get(leftCh))) {
                        // 满足的字符个数-1
                        valid--;
                    }
                    // 将当前字符的数量-1
                    window.put(leftCh, window.get(leftCh) - 1);
                }
            }
        }
        return false;
    }
}
